import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class Graph {
     /*
        4.2 Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
      */
    public static boolean isThereAnyPath(Node n1, Node n2) {
        if (n1 == null || n2 == null) return false;
        if (n1 == n2) return true;
        Queue<Node> nodesToVisit = new LinkedList<Node>();
        Set<Node> visitedNodes = new HashSet<Node>();
        nodesToVisit.add(n1);

        while (!nodesToVisit.isEmpty()) {
            Node currentNode = nodesToVisit.poll();
            if (currentNode.id == n2.id) return true;
            visitedNodes.add(currentNode);
            for (Node adjNode : currentNode.adjacentNodes) {
                if (!visitedNodes.contains(adjNode)) nodesToVisit.add(adjNode);
            }
        }
        return false;
    }


    public static void main(String[] args) {
        Node n1 = new Node(), n2 = new Node(), n3 = new Node(), n4 = new Node(), n5 = new Node();
        n1.connectTo(n2);
        n1.connectTo(n3);
        n3.connectTo(n4);
        n3.connectTo(n5);
        System.out.println("Are they connected? " + n2 + " -- ? --> " + n5 + "   : " + isThereAnyPath(n1, n4));
    }

    private static class Node {
        private static int counter = 1;
        private final int id;
        private Set<Node> adjacentNodes = new HashSet<Node>();

        private Node() {
            this.id = counter++;
        }

        public void connectTo(Node n) {
            if (n == null) return;
            n.adjacentNodes.add(this);
            this.adjacentNodes.add(n);
        }

        @Override
        public String toString() {
            StringBuilder result = new StringBuilder("Node{id=" + id);
            if (!adjacentNodes.isEmpty()) {
                result.append(" Connected to [ ");
                for (Node adjNode : adjacentNodes) result.append(adjNode.id + " ");
                result.append("] ");
            }
            return result.append("}").toString();
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Node node = (Node) o;

            if (id != node.id) return false;

            return true;
        }

        @Override
        public int hashCode() {
            return id;
        }
    }
}
